package com.wx.algorithm.sort;

import com.wx.ArrayUtils;

/**
 * @ClassName SimpleHeapSort
 * @Author wx
 * @Description 代码简化版堆排
 * 时间复杂度O(n * long(n))
 * 空间复杂度O(1)
 * @Date 2020-03-29-12:13
 */
public class SimpleHeapSort {

    public static void sort(int[] array) {
        if (ArrayUtils.arrayValidation(array)) {
            return;
        }

        //构建最大堆
        for (int i = 0; i < array.length; i++) {
            int index = i;
            while (array[index] >  array[(index - 1) / 2]){
                ArrayUtils.swop(array,index,(index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        //排序
        sortRun(array,array.length);
    }

    private static void sortRun(int[] array,int length){
        --length;
        if (length > 0 ){
            //最大值与最后下标交换
            ArrayUtils.swop(array,0,length);

            int index = 0;
            int maxIndex = 0;

            while ((index * 2) + 1 < length){
                int l = (index * 2) + 1;
                int r = l + 1;
                if (r >= length){
                    maxIndex = l;
                } else {
                    maxIndex = array[l] > array[r] ? l : r;
                }
                if (array[maxIndex] > array[index]){
                    ArrayUtils.swop(array,maxIndex,index);
                    index = maxIndex;
                } else {
                    break;
                }
            }
            sortRun(array,length);
        }
    }

    public static void main(String[] agrs){
        ArrayUtils.logarithmicRun(10000,20,10,SimpleHeapSort::sort);;
    }
}
